package june5_13;

import java.util.Stack;

/*
 * Problem Statement And Logic used:
 * Refer the file: "Kth Smallest Integer in BST.log"
 */
public class KthSmallestInteger {

	class Node
	{
		int data;
		int lcount = 0;
		Node left, right;
		
		public Node (int data)
		{
			this.data = data;
			left = null;
			right = null;
		}
	}

	public class BST
	{
		Node root;
		
		public BST()
		{
			root = null;
		}
		
		public Node createNodes (int[] dataList)
		{
			for (int data : dataList)
			{
				Node newElement = new Node (data);
				
				if (root == null)
					root = newElement;
				else
					insertNode (root, newElement);
			}
			
			return root;
		}
		
		public void insertNode (Node theFlagNode, Node theNode)
		{
			// Using Recursion
//			if (theFlagNode.data > theNode.data)
//			{
//				if (theFlagNode.left == null)
//					theFlagNode.left = theNode;
//				else
//					insertNode (theFlagNode.left, theNode);
//			}
//			else if (theFlagNode.data <= theNode.data)
//			{
//				if (theFlagNode.right == null)
//					theFlagNode.right = theNode;
//				else
//					insertNode(theFlagNode.right, theNode);
//			}
			
			// Without Recursion
			Node currentNode = theFlagNode;
			while (theFlagNode != null)
			{
				currentNode = theFlagNode;
				
				if (theNode.data < theFlagNode.data)
				{
					theFlagNode.lcount++;
					theFlagNode = theFlagNode.left;
				}
				else
					theFlagNode = theFlagNode.right;
			}
			
			// - CurrentNode will denote the node above the NULL
			if (theNode.data < currentNode.data)
				currentNode.left = theNode;
			else
				currentNode.right = theNode;
		}
	}
	
	Node kthSmallestElementInOrder (Node root, int K)
	{
		int count = 0;
		Node kthNode = null;
		Node currentNode = root;
		
		// Traverse to the left extreme, push all the nodes on the way to stack
		while (currentNode != null)
		{
			theStack.push(currentNode);
			currentNode = currentNode.left;
		}

		while (theStack.isEmpty() == false)
		{
			Node poppedNode = theStack.pop();
			count ++;
			if (K == count)
				return poppedNode;
			
			if (poppedNode.right != null)
			{
				Node tempNode = poppedNode.right;
						
				while(tempNode != null)
				{
					theStack.push(tempNode);
					tempNode = tempNode.left;
				}
			}
		}

		return null;
	}
	
	Node kthSmallestElement_Augmented (Node theNode, int K)
	{
		while (theNode != null)
		{
			if (K == theNode.lcount + 1)
				return theNode;
			else if (K > theNode.lcount)
			{
				K = K - (theNode.lcount + 1);
				theNode = theNode.right;
			}
			else
			{
				theNode = theNode.left;
			}
		}
		return null;
	}
	
	Stack<Node> theStack = new Stack<>();
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		int[] dataList = { 20, 8, 22, 4, 12, 10, 14 };
		int k = 3;
		
		KthSmallestInteger theProblemObject = new KthSmallestInteger();
		BST tree = theProblemObject.new BST();
		Node root = tree.createNodes(dataList);

		// Inorder traversal way of solving
		Node kthNode = theProblemObject.kthSmallestElementInOrder(root, k);
		
		if (kthNode != null)
			System.out.println("The data in element - " + k + " : " + kthNode.data);
		else
			System.out.println("There is no element");
		
		// Augmented tree data structure
		kthNode = theProblemObject.kthSmallestElement_Augmented(root, k);
		
		if (kthNode != null)
			System.out.println("The data in element - " + k + " : " + kthNode.data);
		else
			System.out.println("There is no element");
		
	}

}
